﻿#ifndef _FIND_SCC_H_ 
#define _FIND_SCC_H_ 1
/************************************************************************/
/* Xinglong Gao
//2018-8-7
/************************************************************************/

#include <cstdio>
#include <cstdlib>
#include <cstddef>
#include <cmath>
#include <memory>
#include <iostream>
#include <fstream>
#include <string>
#include <cstring>
#include <sstream>
#include <vector>
#include <exception>
#include <cassert>
#include <list>

using namespace std;

#define WHITE 0
#define GRAY 1
#define BLACK 2

struct Node {
	int v;
	char id;
	struct Node * next;
	struct Node* tail;
};

typedef struct Node node;

int min(int x, int y) {
	return x < y ? x : y;
}


typedef uint64_t StateId;
typedef uint64_t LabelId;
class WeigthType;
class FstState;
class FstWeight;
class FstArc;


enum class WeightType
{
	TropicalSemring = 0x000001,
	StringSemring = 0x000004,
	LogSemring=0x0000008,
	MinSemring=0x000010
};




class FstWeight
{
public:
	FstWeight(float weight)
	{
	}

	~FstWeight()
	{
	}

	inline static FstWeight Zero() {
		return FstWeight(0.0f);
	}

	inline static FstWeight One() {
		return FstWeight(1.0f);
	}

	inline const float Value() const {
		return weight_;
	}

	inline WeightType Type() const {
		return type_;
	}
	inline WeightType SetType(WeightType type) {
		type_ = type;
		return type_;
	}
	

	inline FstWeight SetWeight(float new_value) noexcept {
		weight_ = new_value;
		return *this;
	}

	inline void ScaleWeight(float scale_factor) noexcept {
		weight_ *= scale_factor;
	}

	FstWeight Sum(const FstWeight& a, const FstWeight& b, WeightType type) const  {
		FstWeight result(0.0f);
		switch (type)
		{
		case WeightType::TropicalSemring:
			result = MinWeight(a, b);
			break;
		case WeightType::StringSemring:
			break;
		case WeightType::LogSemring:
			break;
		case WeightType::MinSemring:
			break;
		default:
			break;
		}
		return result;
	}

	FstWeight Product(const FstWeight& a, const FstWeight& b, WeightType type) const {
		FstWeight result(0.0f);
		switch (type)
		{
		case WeightType::TropicalSemring:
			result = AddWeight(a, b);
			break;
		case WeightType::StringSemring:
			break;
		case WeightType::LogSemring:
			break;
		case WeightType::MinSemring:
			break;
		default:
			break;
		}
		return result;

	}

private:

	inline FstWeight MinWeight(const FstWeight& a, const FstWeight& b) const noexcept {
		return a.Value() > b.Value() ? b : a;
	}

	inline FstWeight AddWeight(const FstWeight& a, const FstWeight& b) const noexcept {
		WeightType a_type = a.Type(), b_type = b.Type();
		assert(a_type == b_type);
		FstWeight result(0.0f);
		result.SetType(a_type);
		float internal_value = a.Value() + b.Value();
		result.SetWeight(internal_value);
		return result;
	}


	float weight_;
	WeightType type_;
};


class FstArc {
public:
	FstArc(LabelId input, LabelId output, FstWeight weight, StateId end) :input_(input),
		output_(output),
		end_(end),
	weight_(weight), weight_scale_(1.0f){};

	virtual ~FstArc() {};

	inline void ReAssignWeight(const FstWeight& weight) {
		weight_ = weight;
	}

	inline void ScaleWeight(float scale_factor) {
		weight_.ScaleWeight(scale_factor);
	}

private:
	StateId end_;
	LabelId input_;
	LabelId output_;
	FstWeight weight_;
	float weight_scale_;
	

};



class FstState
{
public:
	FstState():id_(0), weight_(FstWeight::Zero())
	{
	}

	virtual ~FstState()
	{
	}

	inline FstWeight SetFinal(FstWeight weight) {
		weight_ = weight;
	}

	inline FstWeight Final() const {
		return weight_;
	}

	void AddArc(FstArc* new_arc) {
		links_.push_back(new_arc);
	}

private:
	StateId id_;
	FstWeight weight_;
	vector<FstArc*> links_;
};




class SimpleFst
{
public:
	SimpleFst() {};
	virtual ~SimpleFst() {
		for (auto arc_it = arcs_.begin(); arc_it != arcs_.end();arc_it++)
		{
			delete *arc_it;
		}
		for (auto state_it = states_.begin(); state_it != states_.end();
			state_it++)
		{
			delete * state_it;
		}
	};

	StateId AddState() {
		StateId state_id = states_.size();
		states_.push_back(new FstState);
		return state_id;
	}

	void AddArc(StateId state_id,  FstArc* arc)
	{
		FstState* s = states_[state_id];
		s->AddArc(arc);
	}

	inline FstWeight SetFinal(FstWeight weight) {
		FstState* final_state = states_[final_];
		final_state->SetFinal(weight);
		return weight;
	}

	inline const FstWeight Final() const {
		const FstState* final_state = states_[final_];
		return final_state->Final();
	}


	void ReadAdjacentTable(const char* adjacent_table) {
		if (! adjacent_table){
			return;
		}

	}
	

private:
	vector<FstState*> states_;
	vector<FstArc*> arcs_;
	StateId start_;
	StateId final_;
};




class SCCCompute
{
public:
	SCCCompute():V(0), E(0),time(0), top(0),
		dfn_first_time_(nullptr),lower_node_back_time_(nullptr), vis(nullptr), reverse_postorder_(nullptr), stack_(nullptr),
		graph(nullptr),reversed_graph(nullptr), first_id_(0)
	{
	}


	SCCCompute(const char* linked_list_table) :V(0), E(0), time(0), top(0),
		dfn_first_time_(nullptr), lower_node_back_time_(nullptr), vis(nullptr), reverse_postorder_(nullptr), stack_(nullptr),
		graph(nullptr),reversed_graph(nullptr), first_id_(0) {
		const uint32_t string_length = 1024;
		int i, u, v;
		// the number of vertexes and edges
		FILE* fp = fopen(linked_list_table, "r");
		int32_t num_vertexes = 0.0f;
		char line_buff[string_length];
		memset(reinterpret_cast<void*>(line_buff), 0, string_length);
		while (!feof(fp))
		{
			fgets(line_buff, string_length, fp);
			char* header = line_buff;
			bool should_continoue = false;
			
			if (*header == '\r' || *header == '\n' || *header == '#') {
				continue;
			}
			else
			{
				while (*header == ' ')
				{
					header++;
					if (*header == '#') {
						should_continoue = true;
						break;
					}
				}
			}
			if (should_continoue) {
				continue;
			}
			num_vertexes++;
		}
		fseek(fp, 0, SEEK_SET);
		graph = (node **)malloc(sizeof(node *) * (num_vertexes + 1));
		for (i = first_id_; i <= num_vertexes; i++)
			graph[i] = nullptr;
		V = num_vertexes;
		while (!feof(fp))
		{
			fgets(line_buff, string_length, fp);
			char* header = line_buff;
			bool should_continoue = false;
			if (*header == '\r' || *header == '\n' || *header == '#') {
				continue;
			}
			else {
				while (*header == ' ')
				{
					header++;
					if (*header == '#') {
						should_continoue = true;
						break;
					}
				}
			}

			if (should_continoue) {
				continue;
			}
			uint64_t first_vertex = std::atoi(&line_buff[0]);
			char* dest = line_buff;
			dest++;
			while (*dest != '\0')
			{
				if (*dest != ' ' && *dest != '\r' && *dest != '\n') {
					uint64_t num_v = std::atoi(&dest[0]);
					insert(graph, first_vertex, num_v);
					E++;
				}
				++dest;
			}
			memset(reinterpret_cast<void*>(line_buff), 0, string_length);
		}
		fclose(fp);
		init();
	}

	virtual ~SCCCompute()
	{
		uint32_t first_link = first_id_;
		Node* curr = nullptr, * next = nullptr;
		for (int k = first_link; k <= V; k++)
		{
			curr = graph[k];
			while (curr != nullptr)
			{
				next = curr->next;
				delete curr;
				curr = next;
			}
		}
		free(graph);
		for (int i=first_link;i<=V;i++)
		{
			curr = reversed_graph[i];
			while (curr != nullptr)
			{
				next = curr->next;
				delete curr;
				curr = next;

			}
		}
		free(reversed_graph);
		free(reverse_postorder_);
		free(dfn_first_time_);
		free(lower_node_back_time_);
		free(vis);
		free(stack_);
	}

	// insert to adjacent list
	inline void insert(node ** graph, int u, int v) {
		node * temp = (node *)malloc(sizeof(node));
		temp->v = v;
		temp->next = graph[u];
		graph[u] = temp;
	}

	inline void ReverseSelf(Node** graph) {
		if (graph==nullptr){
			return;
		}
		if (reversed_graph){
			uint32_t first_link = first_id_;
			Node* curr = nullptr, *next = nullptr;
			for (int k = first_link; k <= V; k++)
			{
				curr = reversed_graph[k];
				while (curr != nullptr)
				{
					next = curr->next;
					delete curr;
					curr = next;
				}
			}
			free(reversed_graph);
		}
		reversed_graph = (node **)malloc(sizeof(node *) * (V + 1));
		for (uint32_t i = first_id_; i <= V; i++)
			reversed_graph[i] = nullptr;
		// Real implementation for reverse current graph
		Node* curr = nullptr, *next = nullptr;
		for (uint32_t k = first_id_; k<V; k++)
		{
			curr = graph[k];
			while (curr != nullptr)
			{
				uint32_t dest = curr->v;
				insert(reversed_graph, dest, k);
				next = curr->next;
				curr = next;
			}
		}

	}


	inline void Topological(node ** graph, int * indegree) {
		if (! indegree){
			indegree = (int *)malloc(sizeof(int) * (V + 1));
		}
		queue<int> S;
		std::list<int> L;
		for (int i = 1; i <= V; i++) {
			if (!indegree[i])
				S.push(i);
		}
		while (!S.empty()) {
			int u = S.front();
			S.pop();
			L.push_back(u);
			node * temp = graph[u];
			while (temp != NULL) {
				E--;
				if (!--indegree[temp->v])
					S.push(temp->v);
				temp = temp->next;
			}
		}
		if (E != 0)
			cout << "G has Circuit";
		else
			for (auto i = L.begin(); i != L.end(); ++i)
				cout << *i << " ";
		cout << endl;
	}


	//http://blog.forec.cn/2015/09/19/Graph-Algorithms3/
	inline void Tarjan(node ** graph, int u) {
		dfn_first_time_[u] = lower_node_back_time_[u] = ++time;
		stack_[top++] = u;
		vis[u] = GRAY;
		// get root node of current sub graph
		// get node u as root 
		node * temp = graph[u];
		while (temp != NULL) {
			if (vis[temp->v] == WHITE) {
				Tarjan(graph, temp->v);
				lower_node_back_time_[u] = min(lower_node_back_time_[u], lower_node_back_time_[temp->v]);
			}
			if (vis[temp->v] == GRAY)
				lower_node_back_time_[u] = min(lower_node_back_time_[u], dfn_first_time_[temp->v]);
			temp = temp->next;
		}
		vis[u] = BLACK;
		if (dfn_first_time_[u] == lower_node_back_time_[u]) {
			printf("Current Scc group : ");
			while (stack_[--top] != u)
				printf("%d ", stack_[top]);
			printf("%d\n", u);
		}
	}

	inline void Tarjan_Graph(node ** graph) {
		dfn_first_time_ = (int *)malloc(sizeof(int) * (V + 1));
		lower_node_back_time_ = (int *)malloc(sizeof(int) * (V + 1));
		vis = (int *)malloc(sizeof(int) * (V + 1));
		stack_ = (int *)malloc(sizeof(int) * (V + 1));
		memset(vis, 0, sizeof(int) * (V + 1));
		int i;
		for (i = 1; i <= V; i++)
			if (vis[i] == WHITE)
				Tarjan(graph, i);
	}

	inline void AllocateNodes(uint64_t num_node) {
		
	}

	inline int Tarjan_print(const char* list_table) noexcept
	{
		const uint32_t string_length = 1024;
		int i, u, v;
		// the number of vertexes and edges
		FILE* fp = fopen(list_table, "r");
		int32_t num_vertexes = 0.0f;
		char line_buff[string_length];
		memset(reinterpret_cast<void*>(line_buff), 0, string_length);
		while ( ! feof(fp))
		{
			fgets(line_buff, string_length, fp);
			char* header = line_buff;
			bool should_continoue = false;
			while ( *header == ' ')
			{
				header++;
				if (*header == '#'){
					should_continoue = true;
					break;
				}
			}
			if (*header == '\r' || *header == '\n'){
				continue;
			}
			if (should_continoue){
				continue;
			}
			num_vertexes++;
		}
		fseek(fp, 0, SEEK_SET);
		graph = (node **)malloc(sizeof(node *) * (num_vertexes + 1));
		for (i = first_id_; i <= num_vertexes; i++)
			graph[i] = nullptr;
		V = num_vertexes;
		while (!feof(fp))
		{
			fgets(line_buff, string_length, fp);
			char* header = line_buff;
			bool should_continoue = false;
			while (*header == ' ')
			{
				header++;
				if (*header == '#') {
					should_continoue = true;
					break;
				}
			}
			if (*header == '\r' || *header == '\n') {
				continue;
			}
			if (should_continoue) {
				continue;
			}
			uint64_t first_vertex = std::atoi(&line_buff[0]);
			char* dest = line_buff;
			dest++;
			while (*dest != '\0')
			{
				if (*dest != ' ' && *dest != '\r' && *dest != '\n'){
					uint64_t num_v = std::atoi(&dest[0]);
					insert(graph, first_vertex, num_v);
					E++;
				}
				++dest;
			}
			memset(reinterpret_cast<void*>(line_buff), 0, string_length);
		}
		fclose(fp);
		Tarjan_Graph(graph);
		return 0;
	}

	void Dfs_Visit(node ** graph, int u) {
		printf("hit : %d ", u);
		vis[u] = GRAY;
		node * temp = graph[u];
		while (temp != nullptr) {
			if (vis[temp->v] == WHITE)
				Dfs_Visit(graph, temp->v);
			temp = temp->next;
		}
		vis[u] = BLACK;
		stack_[top++] = u;
	}

	void Dfs( node ** graph) {
		int i;
		top = 0;
		for (i = first_id_; i <= V; i++)
			vis[i] = 0;
		for (i = first_id_; i <= V; i++)
			if (vis[reverse_postorder_[i]] == WHITE) {
				Dfs_Visit(graph, reverse_postorder_[i]);
				putchar('\n');
			}
	}

	void init() {
		vis = (int *)malloc(sizeof(int) * (V + 1));
		stack_ = (int *)malloc(sizeof(int) * (V + 1));
		reverse_postorder_ = (int *)malloc(sizeof(int) * (V + 1));
		int i;
		for (i = first_id_; i <= V; i++)
			reverse_postorder_[i] = i;
	}

	// https://www.cnblogs.com/nullzx/p/6437926.html
	inline void FindSccUsingKosaraju() {
		if (graph) {
			ReverseSelf(graph);
		}

		node** graph_self = Graph();
		// get reversed graph
		Node** graph_revsersed = ReversedGraph();
		// get order of nodes
		Dfs(graph_revsersed);
		for (int32_t i  = first_id_; i <= V; i++)
			reverse_postorder_[i] = stack_[--top];
		std::cout << "Result:\n";
		Dfs(graph);
	}


	Node** Graph() const {
		return graph;
	}

	Node** ReversedGraph() const {
		return reversed_graph;
	}


	inline void ReadAdjacentMatrix(const char* adjacent_matrix_file) {

	}



	inline void ReadAdjacentTable(const char* adjacent_table_file) {
		if (! adjacent_table_file){
			return;
		}

		std::ifstream is(adjacent_table_file, ios::in);
		try
		{
			if (is.is_open()) {
				string token, table_line;
				is >> std::ws;
				while ( ! is.eof())
				{

				}

			}

		}
		catch (const std::exception&e)
		{
			
			is.close();
			std::cout << e.what();

		}
		is.close();

	}

public:
	int V;
	int E;
	int time;
	int32_t first_id_;
	Node** graph;
	Node** reversed_graph; //For koraju

	int * dfn_first_time_;
	int *lower_node_back_time_;
	int * vis;
	int * stack_;
	int* reverse_postorder_;
	int top;
private:

};




#endif